package 力扣日常刷题.木22一月.第05天0112;

/**
 * @author 帅小伙
 * @date 2022/1/12
 * @description
 * 没看懂
 * https://leetcode-cn.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/submissions/
 */
public class Demo04回溯中等长度为n的开心字符串中字典序第k小的字符串 {


    class Solution {
        public String getHappyString(int n, int k) {
            int count=3<<(n-1);//3*2^(n-1)
            if(k>count) return "";
            char[] result=new char[n];
            int[][] stateTab=new int[][]{{1,2},{0,2},{0,1}};
            //状态0,1,2分别表示a,b,c，
            //转移参数：0表示下一个取较小的字符，1表示下一个取较大的字符
            int order=k-1;//序号k-1,表示第k大
            int index=0 ,state= order>>(n-1);// <=>order/2^(n-1)
            result[index++]=(char)(state+'a');
            int tree=order&((1<<(n-1))-1);//获取其在树中的位置<=>order% 2^(n-1)
            for(int i=n-2;i>=0;i--){
                state=stateTab[state][(tree >> i) & 1];//(tree >> i) & 1取二进制第i位
                result[index++]=(char)(state+'a');
            }
            return String.valueOf(result);
        }
    }


}
